【题解】 [SDOI2015]约数个数和莫比乌斯反演 luoguP3327

又是一道神奇的题目。

一句话题意：给定 $n,m$ 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$

于是开始推式子：

有这么一条公式：

$d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$

这个非常重要，至于证明的话，本人太弱，留个坑，到时候再填，请大家谅解 $QwQ$ 。

然后呢？发现题目求的式子后面正好是 $d(ij)$ ，于是美滋滋的套进去。

$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(i,j)=1]$

$x$ 和 $y$ 我们扔到前面去枚举，后面来计算它们对它们的倍数做出的贡献。

可以知道前面的 $x$ 在 $n$ 以内的倍数有 $\lfloor\frac{n}{x}\rfloor$ 个，$y$ 在 $m$ 以内的倍数有 $\lfloor\frac{m}{y}\rfloor$，于是：

$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(i,j)=1]$ $=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=1]$

按照套路，我们设：

$f(x)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[gcd(i,j)=k]$ $g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$

那么显然有：

$g(k)=\sum_{k|d} f(d)$

这个式子很有熟悉的味道，显然是反演常见的第二种形式。

所以就有：

$f(k)=\sum_{k|d}\mu(\frac{d}{k})g(d)$

我们的答案是$f(1)$，那么就是：

$f(1)=\sum_{d=1}^{n}\mu(d)g(d)$

现在来考虑怎么计算 $g$ 。

$g(k)=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\cdot[k|gcd(i,j)]$

后面的 $k$ 很碍眼，消掉他。

$g(k)=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor$

于是我们预处理一个函数 $s$ ：

$s(k)=\sum_{i=1}^{k}\lfloor\frac{k}{i}\rfloor$

那么 $g(k)$ 就很好算了：

$g(k)=s(n/k) \cdot s(m/k)$

复杂度的话还好，预处理 $s$ 时可以整出分块，$O(\sqrt{n})$ 爽歪歪。然后的话，发现统计答案的时候 $g$ 函数也可以整出分块，$O(\sqrt{n})$ 。最后总时间复杂度 $O(T\sqrt{n})$ (???)反正过了就行，我也不会算 $QwQ$ 。

Code:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define ll long long
#define min(x,y) ((x)<(y)?(x):(y))

const int N=5e4+2;
const int inf=1e9+9;

int T,n,m,cnt;
int mui[N],vis[N],prime[N];
ll s[N]; 

inline void _pre_mui(){
    mui[1]=1;
    for(int i=2;i<=N;++i){
        if(!vis[i])prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt;++j){
            if(i*prime[j]>5e4)break;
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
            mui[i*prime[j]]=-mui[i];
        }
    }
    for(int i=1;i<=N;++i)mui[i]+=mui[i-1];
    for(int x=1;x<=N;++x){//实际上这里是O(n sqrt(n))，不过影响不大。
        ll res=0;
        for(int l=1,r=0;l<=x;l=r+1)
            r=(x/(x/l)),res+=1ll*(r-l+1)*(x/l);
        s[x]=res;
    }return;
}

inline ll solve(int n,int m){
    ll ans=0;
    if(n>m)n^=m^=n^=m;
    for(int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*(mui[r]-mui[l-1])*s[n/l]*s[m/l];
    }return ans;
}

int main(){
    _pre_mui();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%lld\n",solve(n,m));
    }return 0;
}

$=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]ij$

本文标题:【题解】 [SDOI2015]约数个数和莫比乌斯反演 luoguP3327

文章作者:Qiuly

发布时间:2019年03月01日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/03/01/[题解]luoguP3327/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。